#pragma once
#include "AbstractSymbolTable.h"
#include <iostream>
#include <vector>
#include <queue>
template<typename Comp, typename ValType>
class Node{
public:
	Comp key;
	ValType value;
	Node * left;
	Node * right;
	Node(const Comp&_key, const ValType & _val, Node * _left = nullptr, Node * _right = nullptr) :key(_key), value(_val), left(_left), right(_right)
	{

	}
};

template<typename Comp,typename ValType>
class BSTreeSymbolTable:public AbstractSymbolTable<Comp,ValType>
{
public:

	typedef Node<Comp, ValType>* nodeptr;
	BSTreeSymbolTable() :root(nullptr)
	{

	}
	~BSTreeSymbolTable()
	{

	}


	void reveal(){
		levelOrdered(root);
	}

	void put( const Comp & key,  const ValType & value);

	ValType get(const Comp&obj);
private:
	Node<Comp,ValType> * root;
	
	template<typename Comp, typename ValType>
	void levelOrdered(Node<Comp, ValType> * root){
		
		std::vector<std::vector<nodeptr>> levels;
		std::queue<nodeptr> outer;
		std::queue<nodeptr> inner;
		outer.push(root);

		while (!outer.empty())
		{
			std::vector<nodeptr> tmp;
			while (!outer.empty())
			{
				nodeptr node = outer.front();
				
				tmp.push_back(node);
				
				if (node->left != nullptr)
					inner.push(node->left);
				if (node->right != nullptr)
					inner.push(node->right);
				outer.pop();
				
			}
			levels.push_back(tmp);
			while (!inner.empty())
			{
				nodeptr node = inner.front();
				outer.push(node);
				inner.pop();
			}



		}
		
		for (auto vec : levels)
		{
			for (nodeptr node : vec)
			{
				std::cout << node->key << " ";
			}
			std::cout << std::endl;
		}

	}


	template<typename Comp, typename ValType>
	void backSeqPrint(Node<Comp, ValType> * root)
	{
		if (root == nullptr)
			return;
		
		backSeqPrint(root->left);
		std::cout << root->key << std::endl;
		backSeqPrint(root->right);
	}


	template<typename Comp, typename ValType>
	void insert(Node<Comp, ValType> *& root, const Comp& key, const ValType & value)
	{
		if (root == nullptr){
			root = new Node<Comp, ValType>(key, value);
			return;
		}
			
		else if (key > root->key)
			insert(root->right, key, value);
		else if (key < root->key)
			insert(root->left, key, value);
		else
			return;
	}


	template<typename Comp, typename ValType>
	Node<Comp, ValType> * find(Node<Comp, ValType> * root, const Comp&key)
	{
		if (root == nullptr)
			return nullptr;

		if (root->key == key)
			return root;
		else if (key > root->key)
			return find(root->right, key);
		else if (key < root->key)
			return find(root->left, key);
		
	}

};


template<typename Comparable, typename ValueType>
ValueType BSTreeSymbolTable<Comparable, ValueType>::get(const Comparable& key)
{
	Node<Comparable, ValueType> * node = this->find(root, key);
	if (node != nullptr)
		return node->value;
	else
		return ValueType();
		
}

template<typename Comparable, typename ValueType>
void BSTreeSymbolTable<Comparable, ValueType>::put(const Comparable& key,const ValueType  & val)
{
	this->insert(root, key, val);
}